package com.lft.graph06.topological_sort;

/**
 * 拓扑排序
 */
public class TopologicallySortDemo {
	public static void main(String[] args) {
		Graph graph = new Graph(8);
		graph.addVertex("A"); // 0
		graph.addVertex("B"); // 1
		graph.addVertex("C"); // 2
		graph.addVertex("D"); // 3
		graph.addVertex("E"); // 4
		graph.addVertex("F"); // 5
		graph.addVertex("G"); // 6
		graph.addVertex("H"); // 7
		
		graph.addEdge(0, 3);
		graph.addEdge(0, 4);
		graph.addEdge(1, 4);
		graph.addEdge(2, 5);
		graph.addEdge(3, 6);
		graph.addEdge(4, 6);
		graph.addEdge(5, 7);
		graph.addEdge(6, 7);
		
		graph.topologicallySort();
	}
}

/**
 * 顶点类
 */
class Vertex {
	String label;
	
	public Vertex(String label) {
		this.label = label;
	}
}

class Graph {
	/**
	 * 顶点数组列表
	 */
	Vertex[] vertexList;
	/**
	 * 邻接矩阵
	 */
	int[][] adjacencyMatrix;
	/**
	 * 顶点数量
	 */
	int numOfVertexes;
	/**
	 * 排序的 char 数组
	 */
	String[] sortedArray;
	
	/**
	 * 构造器 用传入的顶点数量初始化 各个域
	 * @param maxNumOfVertex
	 */
	public Graph(int maxNumOfVertex) {
		vertexList = new Vertex[maxNumOfVertex];
		adjacencyMatrix = new int[maxNumOfVertex][maxNumOfVertex];
		numOfVertexes = 0;
		for (int i = 0; i < maxNumOfVertex; i++) {
			for (int j = 0; j < maxNumOfVertex; j++) {
				adjacencyMatrix[i][j] = 0;
			}
		}
		sortedArray = new String[maxNumOfVertex];
	}
	
	/**
	 * 添加顶点
	 * @param label
	 */
	public void addVertex(String label) {
		vertexList[numOfVertexes++] = new Vertex(label);
	}
	
	/**
	 * 添加边 0 表示不通。1 表示连通
	 * @param start
	 * @param end
	 */
	public void addEdge(int start, int end) {
		adjacencyMatrix[start][end] = 1;
		// 无向图可以添加下面的代码
		// adjacencyMatrix[end][start] = 1;
	}
	
	/**
	 * 打印顶点
	 * @param vertexIndex
	 */
	public void displayVertex(int vertexIndex) {
		System.out.println(vertexList[vertexIndex].label + "");
	}
	
	/**
	 * 拓扑排序方法
	 */
	public void topologicallySort() {
		// 定义一个临时变量 保存原始顶点的数量。
		int original_numOfVertex = numOfVertexes;
		// 循环遍历，只根顶点数量大于0
		while (numOfVertexes > 0) {
			// 判断是否有后继顶点。
			int curIndex = noSuccessors();
			// 如果是环。
			if (curIndex == -1) {
				// 输出错误信息。
				System.out.println("error:graph has cycles");
				// 结束方法
				return;
			}
			// 不是环。将当前顶点的标签，从后往前放在排序数组中。
			sortedArray[numOfVertexes - 1] = vertexList[curIndex].label;
			// 执行删除当前顶点操作。
			deleteVertex(curIndex);
		}
		// 下面是打印输出排好序的顶点。
		System.out.print("Topologically Sorted Order:");
		for (int i = 0; i < original_numOfVertex; i++) {
			System.out.print(sortedArray[i] + "\t");
		}
		System.out.println();
	}
	
	/**
	 * 判断是否有后继顶点
	 * @return
	 */
	private int noSuccessors() {
		// 定义一个临时布尔变量，用于判断是否是边
		boolean isEdge;
		// 循环遍历行
		for (int row = 0; row < numOfVertexes; row++) {
			// 初始化 false
			isEdge = false;
			// 循环遍历列
			for (int col = 0; col < numOfVertexes; col++) {
				// 如果邻接矩阵的权重大于0说明 是边。
				if (adjacencyMatrix[row][col] > 0 && adjacencyMatrix[row][col] < Integer.MAX_VALUE) {
					// 说明是边
					isEdge = true;
					// 跳出循环当前 col 循环
					break;
				}
			}
			// 非边
			if (!isEdge) {
				// 将当前的行索引返回
				return row;
			}
		}
		// 循环结束还能被执行到表示有环，返回 -1
		return -1;
	}
	
	/**
	 * 删除顶点
	 * @param vertexIndex
	 */
	private void deleteVertex(int vertexIndex) {
		if (vertexIndex != (numOfVertexes - 1)) {
			// 遍历 顶点列表。
			for (int i = vertexIndex; i < numOfVertexes - 1; i++) {
				// 删除顶点列表中的顶点，只需要将后面的所有顶点均往前移一位，覆盖删除的顶点。
				vertexList[i] = vertexList[i + 1];
			}
			// 删除一个顶点之后，行要上移一行。
			for (int row = vertexIndex; row < numOfVertexes - 1; row++) {
				moveRowUp(row, numOfVertexes);
			}
			// 删除一个顶点之后，列要左移一列
			for (int col = vertexIndex; col < numOfVertexes - 1; col++) {
				moveColLeft(col, numOfVertexes - 1);
			}
		}
		// 顶点数量-1
		numOfVertexes--;
	}
	
	/**
	 * 上移行方法
	 * @param row
	 * @param numOfVertexes
	 */
	private void moveRowUp(int row, int length) {
		for (int col = 0; col < length; col++) {
			adjacencyMatrix[row][col] = adjacencyMatrix[row + 1][col];
		}
	}
	
	/**
	 * 左移列方法
	 * @param col
	 * @param length
	 */
	private void moveColLeft(int col, int length) {
		for (int row = 0; row < length; row++) {
			adjacencyMatrix[row][col] = adjacencyMatrix[row][col + 1];
		}
	}
	
}


